#!/usr/bin/env python
# -*- coding:utf-8 -*-
# @Author  : 邢建辉
# @Email   : xjh_0125@sina.com
# @Time    : 2021/12/28 14:09
# @Software: PyCharm
# @File    : l23_is_magic.py


class Solution(object):
    def __init__(self):
        '''
        1.先洗牌得到sort，
        2.对比sort与targe的最长相同位数得到最大k
        3.从k,1倒叙走洗牌，取牌流程，判断时候满足条件
        '''
        pass

    def isMagic(self, target):
        """
        :type target: List[int]
        :rtype: bool
        """
        total = len(target)
        sort = Solution.magic_sort([i + 1 for i in range(total)])
        max_k = Solution.same_count(target, sort)
        if max_k == 0:
            return False
        min_k = 0
        if max_k > 1 and total >= 2:
            first_step = sort[1] - sort[0]
            for i in range(total - 1):
                if sort[i + 1] - sort[i] == first_step:
                    min_k += 1
                else:
                    break
        min_k = max(min_k - 1, 0)
        if min_k >= max_k:
            min_k = 0
        print(max_k, min_k)
        for i in range(max_k, min_k, -1):
            taked = []
            rest = [j for j in sort]
            while len(rest) > 0:
                taked.extend(rest[0:max_k])
                if max_k < len(rest):
                    rest = Solution.magic_sort(rest[max_k:])
                else:
                    break
            if Solution.same_count(taked, target) == total:
                print(i)
                return True
        return False

    @staticmethod
    def magic_sort(list):
        c = len(list) + 1
        tmp = list[1:c:2]
        tmp.extend(list[0: c:2])
        return tmp

    @staticmethod
    def same_count(li1, li2):
        k = 0
        for i in range(len(li1)):
            if li1[i] == li2[i]:
                k += 1
            else:
                break
        return k


if __name__ == '__main__':
    s = Solution()
    li = [2, 4, 6, 10, 14, 18, 26, 34, 42, 15, 31, 8, 40, 29, 38, 20, 41, 16, 35, 13, 36, 12, 23, 24, 37, 30, 28, 27,
          17, 22, 25, 7, 1, 9, 11, 21, 5, 19, 43, 33, 32, 39, 3]
    print(s.isMagic(li))
